package org.kk.str;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * 字符串排列
 */
public class Permutation {
    private static List<String> result = new LinkedList<>();
    private static char[] c;

    /**
     * 示例
     * 输入：s = "abc"
     * 输出：["abc","acb","bac","bca","cab","cba"]
     */
    public static String[] permutation(String s){
        c = s.toCharArray();
        dfs(0);
        return result.toArray(String[]::new);
    }
    private static void dfs(int x){
        if (x == c.length -1) {
            result.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i, x);
            dfs(x + 1);
            swap(i, x);
        }
    }
    private static void swap(int i, int x){
        char temp = c[i];
        c[i] = c[x];
        c[x] = temp;
    }
}
